/*数组中占比超过一半的元素称之为主要元素。给你一个 整数 数组，找出其中的主要元素。若没有，返回 -1 。
* 请设计时间复杂度为 O(N) 、空间复杂度为 O(1) 的解决方案。
*
* 输入：[1,2,5,9,5,9,5,5,5]
* 输出：5
* */

package Leetcode;

import java.util.Deque;
import java.util.LinkedList;

public class Interview_questions17_10 {

    public static void main(String[] args) {

        Interview_questions17_10 obj = new Interview_questions17_10();
        int[] nums = {3, 2};
        System.out.println(obj.majorityElement(nums));
    }

    //摩尔投票
    public int majorityElement(int[] nums){

        int count = 1, major = nums[0];
        for (int i = 1; i < nums.length; i++) {

            if (nums[i] == major){
                count++;
            }else {
                count--;
                if (count == 0){
                    major = nums[i];
                    count = 1;
                }
            }
        }
        int res = 0;
        for (int num : nums){
            if (num == major){
                res++;
            }
        }
        return res > nums.length / 2?major:-1;
    }
}
